class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int> > dp(word1.size(),vector<int>(word2.size(),0));
        if(word1[0] != word2[0]) dp[0][0] = 2;
        for(int i = 1;i < word1.size();i++){
            if(word2[0] == word1[i]){
                dp[i][0] = i;
            }else{
                dp[i][0] = dp[i - 1][0] + 1;
            }
        }
        
        for(int j = 1;j < word2.size();j++){
            if(word2[j] == word1[0]){
                dp[0][j] = j;
            }else{
                dp[0][j] = dp[0][j- 1] + 1;
            }
        }
        for(int i = 1;i < word1.size();i++){
            for(int j = 1;j < word2.size();j++){
               if(word1[i] == word2[j]){
                   dp[i][j] = dp[i - 1][j - 1];
               } else{
                   dp[i][j] = min({dp[i - 1][j]+1,dp[i][j - 1]+1,dp[i-1][j-1]+2});
               }
            }
        }
        
        
        return dp[word1.size() - 1][word2.size() - 1];
    }
};
